
"""
297. 二叉树的序列化与反序列化
"""
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Codec:

    def __init__(self):
        self.sep = ','
        self.null = '#'
        self.strs = ''
        self.count = 0

    def serialize(self, root):
        self.traverse(root)
        return self.strs
    """
     * 使用前序遍历
     * 各节点以逗号隔开，#代表空节点
    """
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            self.strs += self.null + self.sep
            return
        # 前序位置
        self.strs += str(root.val) + self.sep
        self.traverse(root.left)
        # 中序位置
        self.traverse(root.right)
        # 后序位置

    """
    利用分解二叉树构建二叉树
    注：由于是满二叉树，所以只需要前序遍历即可构建
    """
    def deserialize(self, data):
        if not data:
            return None
        strs = data.split(self.sep)
        return self.traverse1(strs)

    '''遍历二叉树'''
    def traverse1(self, strs : List[int]):
        if self.count == len(strs) - 1:
            return None
        if self.null == strs[self.count]:
            return None
        # 前序位置
        root = TreeNode(strs[self.count])
        self.count += 1
        root.left = self.traverse1(strs)
        # 中序位置
        self.count += 1
        root.right = self.traverse1(strs)
        # 后序位置
        return root